{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Length of the Longest Subsequence That Sums to Target"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lengthOfLongestSubsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #和为目标值的最长子序列的长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>target</code>&nbsp;。</p>\n",
    "\n",
    "<p>返回和为 <code>target</code>&nbsp;的 <code>nums</code>&nbsp;子序列中，子序列&nbsp;<strong>长度的最大值&nbsp;</strong>。如果不存在和为 <code>target</code>&nbsp;的子序列，返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>子序列</strong> 指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,3,4,5], target = 9\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>总共有 3 个子序列的和为 9 ：[4,5] ，[1,3,5] 和 [2,3,4] 。最长的子序列是 [1,3,5] 和 [2,3,4] 。所以答案为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [4,1,3,2,1,5], target = 7\n",
    "<b>输出：</b>4\n",
    "<strong>解释：</strong>总共有 5 个子序列的和为 7 ：[4,3] ，[4,1,2] ，[4,2,1] ，[1,1,5] 和 [1,3,2,1] 。最长子序列为 [1,3,2,1] 。所以答案为 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,1,5,4,5], target = 3\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>无法得到和为 3 的子序列。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= target &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [length-of-the-longest-subsequence-that-sums-to-target](https://leetcode.cn/problems/length-of-the-longest-subsequence-that-sums-to-target/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [length-of-the-longest-subsequence-that-sums-to-target](https://leetcode.cn/problems/length-of-the-longest-subsequence-that-sums-to-target/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]\\n9', '[4,1,3,2,1,5]\\n7', '[1,1,5,4,5]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        f = [0] + [-inf] * target\n",
    "        s = 0\n",
    "        for x in nums:\n",
    "            s = min(s+x,target)\n",
    "            for j in range(s,x-1,-1):\n",
    "                if f[j] < f[j-x] + 1:\n",
    "                    f[j] = f[j-x] + 1\n",
    "        return f[-1] if f[-1] > 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        nums = Counter(nums)\n",
    "        \n",
    "        keys = list(nums.keys())\n",
    "        \n",
    "        n = len(keys)\n",
    "        \n",
    "        dp = [[0] * (target+1) for _ in range(n)]\n",
    "        \n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(target, -1, -1):\n",
    "                for k in range(nums[keys[i]]+1):\n",
    "                    if k * keys[i] > j:\n",
    "                        break\n",
    "                    if i == 0:\n",
    "                        if k * keys[i] != j:\n",
    "                            continue\n",
    "                        dp[i][j] = max(dp[i][j], k)\n",
    "                    else:\n",
    "                        if dp[i-1][j - k * keys[i]] != 0:\n",
    "                            dp[i][j] = max(k+dp[i-1][j - k * keys[i]], dp[i][j])\n",
    "                        elif j - k * keys[i] == 0:\n",
    "                            dp[i][j] = max(dp[i][j], k)       \n",
    "              \n",
    "        return dp[-1][-1] if dp[-1][-1] != 0 else -1\n",
    "                        \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        dp = [[-1] * (target + 1) for _ in range(n + 1)]\n",
    "        for i in range(n + 1):\n",
    "            dp[i][0] = 0\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, target + 1):\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                if j - nums[i - 1] >= 0 and dp[i - 1][j - nums[i - 1]] != -1:\n",
    "                  dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - nums[i - 1]])\n",
    "        return dp[n][target]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i,c):\n",
    "        #     if i < 0:\n",
    "        #         return 0 if c == 0 else -inf\n",
    "        #     if c < nums[i]:\n",
    "        #         return dfs(i-1, c)\n",
    "        #     return max(dfs(i-1, c), dfs(i-1, c-nums[i]) + 1)\n",
    "        # ans = dfs(n-1, target)\n",
    "        # return ans if ans > -inf else -1\n",
    "\n",
    "        f = [[-inf] * (target+1) for _ in range(n+1)]\n",
    "        f[0][0] = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            for c in range(target + 1):\n",
    "                if c < x:\n",
    "                    f[i+1][c] = f[i][c]\n",
    "                else:\n",
    "                    f[i+1][c] = max(f[i][c], f[i][c-nums[i]] + 1)\n",
    "        ans = f[n][target]\n",
    "        return ans if ans > -inf else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        target += 1\n",
    "        info = [[0 for i in range(target)] for j in range(len(nums))]\n",
    "\n",
    "        if nums[0] < target:\n",
    "            info[0][nums[0]] = 1\n",
    "\n",
    "        for j in range(1, len(nums)):\n",
    "            if nums[j] >= target:\n",
    "                for i in range(target):\n",
    "                    info[j][i] = info[j - 1][i]\n",
    "                continue\n",
    "            for i in range(target):\n",
    "                if i - nums[j] >= 0 and (i - nums[j] == 0 or info[j - 1][i - nums[j]] > 0):\n",
    "                    info[j][i] = max(info[j - 1][i - nums[j]] + 1, info[j - 1][i])\n",
    "                else:\n",
    "                    info[j][i] = info[j - 1][i]\n",
    "            # print(j - 1, info[j - 1])\n",
    "            # print(j, info[j])\n",
    "            # print()\n",
    "        return info[-1][-1] if info[-1][-1] > 0 else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, a: list[int], tar: int) -> int:\n",
    "        n, ans = len(a), -1\n",
    "        a.insert(0, 0)\n",
    "        f = [[-10000] * (tar + 2) for _ in range(n + 1)]\n",
    "        f[0][0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            f[i][0] = 0\n",
    "            for j in range(1, tar + 1):\n",
    "                f[i][j] = max(f[i - 1][j], -100000 if j < a[i] else f[i - 1][j - a[i]] + 1)\n",
    "            ans = max(ans, f[i][tar])\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(Solution.lengthOfLongestSubsequence(None, [1000], 9))\n",
    "    print(Solution.lengthOfLongestSubsequence(None, [4, 1, 3, 2, 1, 5], 7))\n",
    "    print(Solution.lengthOfLongestSubsequence(None, [3, 5, 2, 3, 4], 12))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        numLength = len(nums)\n",
    "        nums.sort()\n",
    "        dp = [[0 for i in range(target+1)] for j in range(numLength)] #前i个字符中，和为target的最大长度\n",
    "        \n",
    "        for j in range(1, target+1):\n",
    "            if nums[0] == j:\n",
    "                dp[0][j] = 1\n",
    "            else:\n",
    "                dp[0][j] = -10000\n",
    "        \n",
    "        for i in range(1, numLength):\n",
    "            for j in range(target +1):\n",
    "                # 前i个字符中，和为j的最大长度\n",
    "                if j >= nums[i]:\n",
    "                    dp[i][j] = max(dp[i-1][j], 1+dp[i-1][j-nums[i]])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        \n",
    "        if dp[numLength-1][target]<0:\n",
    "            return -1\n",
    "        else:\n",
    "            return dp[numLength-1][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "        \n",
    "        dp = [[[-1] * (target + 1) for i in range(2)] for j in range(l)]           \n",
    "\n",
    "        dp[0][0][target] = 0\n",
    "        if target >= nums[0]:\n",
    "            dp[0][1][target - nums[0]] = 1\n",
    "        \n",
    "        for i in range(1, l):\n",
    "            for j in range(target):\n",
    "                #if dp[i - 1][0][j] == -1 and dp[i - 1][1][j] == -1:\n",
    "                #    dp[i][0][j] = -1\n",
    "                #else:\n",
    "                dp[i][0][j] = max(dp[i - 1][0][j], dp[i - 1][1][j]) \n",
    "                \n",
    "                if j + nums[i] <= target:\n",
    "                    if dp[i - 1][0][j + nums[i]] != -1 or dp[i - 1][1][j + nums[i]] != -1:\n",
    "                        dp[i][1][j] = max(dp[i - 1][0][j + nums[i]], dp[i - 1][1][j + nums[i]]) + 1\n",
    "                    \n",
    "        ans = 0             \n",
    "        for i in range(l):\n",
    "            if dp[i][1][0] != -1:\n",
    "                ans = max(ans, dp[i][1][0])\n",
    "        \n",
    "        return ans if ans > 0 else -1\n",
    "                        \n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], t: int) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[[-inf]*(t+1) for _ in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            dp[i][0]=0\n",
    "        for i in range(n):\n",
    "            for j in range(t+1):\n",
    "                if j<nums[i]:\n",
    "                    dp[i+1][j]=dp[i][j]\n",
    "                else:\n",
    "                    dp[i+1][j]=max(dp[i][j-nums[i]]+1,dp[i][j])\n",
    "\n",
    "        return dp[-1][t] if dp[-1][t]>-inf else -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[None] * (2000) for i in range(n+2)]\n",
    "        ans = maxLen(nums, 0 ,0,target,dp)\n",
    "        return ans if ans>0 else -1\n",
    "\n",
    "def maxLen(nums, i, res,target,dp):\n",
    "    if dp[i][res]!=None:\n",
    "        return dp[i][res]\n",
    "    if res == target:\n",
    "        dp[i][res] = 0\n",
    "        return dp[i][res] \n",
    "    if res>target:\n",
    "        dp[i][res]  = -math.inf\n",
    "        return dp[i][res] \n",
    "    if i == len(nums):\n",
    "        if res == target:\n",
    "            dp[i][res]  = 0\n",
    "            return dp[i][res] \n",
    "        else:\n",
    "            dp[i][res]  = -math.inf\n",
    "            return dp[i][res] \n",
    "    dp[i][res]  = max(maxLen(nums,i+1,res+nums[i],target,dp)+1 , maxLen(nums,i+1,res,target,dp))\n",
    "    return dp[i][res] \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[-inf for _ in range(target+1)] for _ in range(n+1)]\n",
    "        dp[0][0]=0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(target+1):\n",
    "                dp[i][j] = dp[i-1][j]\n",
    "                if j-nums[i-1]>=0:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-1][j-nums[i-1]]+1)\n",
    "        return dp[-1][-1] if dp[-1][-1]>0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        memo = [[-2] * (target+1) for _ in range(n+1)]\n",
    "\n",
    "        def dfs(i, s):\n",
    "            if s > target:\n",
    "                return -1\n",
    "            if i == n:\n",
    "                return 0 if s == target else -1\n",
    "            if memo[i][s] != -2:\n",
    "                return memo[i][s]\n",
    "            res = -1\n",
    "            res1 = dfs(i+1, s+nums[i])\n",
    "            res2 = dfs(i+1, s)\n",
    "            if res1 > -1:\n",
    "                res = max(res, res1 + 1)\n",
    "            if res2 > -1:\n",
    "                res = max(res, res2)\n",
    "            memo[i][s] = res\n",
    "            return res\n",
    "\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        dp = [[-1 for _ in range(target)] for _ in range(len(nums))]\n",
    "        \n",
    "        def dfs(i: int, v: int) -> int:\n",
    "            if v > target: return -inf\n",
    "            if v == target: return 0\n",
    "            if i >= len(nums): return -inf\n",
    "            if dp[i][v] != -1: return dp[i][v]\n",
    "            res = max(dfs(i + 1, v), dfs(i + 1, v + nums[i]) + 1)\n",
    "            dp[i][v] = res\n",
    "            return res\n",
    "        ans = dfs(0, 0)\n",
    "        return ans if ans > 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        memo = [[-1] * (target+1) for _ in range(n+1)]\n",
    "\n",
    "        def dfs(i, s):\n",
    "            if s == target:\n",
    "                return 0\n",
    "            if s > target or i == n:\n",
    "                return -inf\n",
    "            if memo[i][s] != -1:\n",
    "                return memo[i][s]\n",
    "            res = max(dfs(i+1, s+nums[i]) + 1, dfs(i+1, s))\n",
    "            memo[i][s] = res\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0, 0)\n",
    "        return ans if ans > 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        f = [[-1] * (target + 1) for _ in range(len(nums))]\n",
    "        def dfs(idx, total):\n",
    "            if idx == len(nums):\n",
    "                return 0 if total == 0 else -inf\n",
    "            if f[idx][total] != -1:\n",
    "                return f[idx][total]\n",
    "            res = dfs(idx + 1, total)\n",
    "            if total >= nums[idx]:\n",
    "                res = max(dfs(idx + 1, total - nums[idx]) + 1, res)\n",
    "            f[idx][total] = res\n",
    "            return res\n",
    "        ans = dfs(0, target)\n",
    "        return ans if ans > 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        l=[]\n",
    "        for pos in range(len(nums)):\n",
    "            l.append(defaultdict(int))\n",
    "        l[0][nums[0]]=1\n",
    "        s=nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            v=nums[i]\n",
    "            s+=v\n",
    "            l[i][v]=1\n",
    "            for k in range(min(s+1,target+1)):\n",
    "                v1=l[i-1][k]\n",
    "                v2=l[i-1][k-v]\n",
    "                if v2>0:v2+=1\n",
    "                l[i][k]=max(max(v1,v2),l[i][k])\n",
    "        r=l[-1][target]\n",
    "        if r>0:return r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        @cache\n",
    "        def dp(i, target):\n",
    "            if target == 0: return 0\n",
    "            if i < 0 or target < 0: return -inf\n",
    "            r1 = dp(i - 1, target - nums[i]) + 1\n",
    "            r2 = dp(i - 1, target)\n",
    "            return r1 if r1 > r2 else r2\n",
    "            return max(\n",
    "                dp(i - 1, target - nums[i]) + 1,\n",
    "                dp(i - 1, target)\n",
    "            )\n",
    "        \n",
    "        r = dp(len(nums) - 1, target)\n",
    "        if r == -inf: return -1\n",
    "        del dp\n",
    "        return r\n",
    "\n",
    "        # dp = [-inf] * (target + 1)\n",
    "        # dp[0] = 0\n",
    "        # for i in nums:\n",
    "        #     for t in range(target, i - 1, -1):\n",
    "        #         r = dp[t - i] + 1\n",
    "        #         if r > dp[t]: dp[t] = r\n",
    "        # return -1 if dp[target] == -inf else dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        \n",
    "        @lru_cache(maxsize=None)\n",
    "        def startsfrom(x, t):\n",
    "            if x > n-1:\n",
    "                return -1\n",
    "            if nums[x] > t:\n",
    "                return -1\n",
    "            if nums[x] == t:\n",
    "                return 1\n",
    "            c0 = startsfrom(x+1, t-nums[x])\n",
    "            c1 = startsfrom(x+1, t)\n",
    "            a = -1\n",
    "            if c0 > 0:\n",
    "                a = c0 +1\n",
    "            a = max(a, c1)\n",
    "                \n",
    "            return a\n",
    "        \n",
    "        ans = startsfrom(0, target)\n",
    "        startsfrom.cache_clear()\n",
    "        \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        nums = [x for x in nums if x <= target]\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        # tot = sum(nums)\n",
    "        # if tot < target:\n",
    "        #     return -1\n",
    "        # if tot == target:\n",
    "        #     return n\n",
    "        @cache\n",
    "        def dfs(st, target):\n",
    "            if st >= n or target < nums[st]:\n",
    "                return float('-inf')\n",
    "            # use st, require: st <= n\n",
    "            if target == nums[st]:\n",
    "                ans1 = 1\n",
    "            else:\n",
    "                ans1 = 1 + dfs(st + 1, target - nums[st])\n",
    "            #don't use st\n",
    "            ans2 = dfs(st + 1, target)\n",
    "            return max(ans1, ans2)\n",
    "        ans = max(dfs(0, target), -1)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        # n = len(nums)\n",
    "        # f = [[-inf for _ in range(target+1)] for j in range(n+1)] # 这里每个都要加一\n",
    "        # f[0][0] = 0\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(target+1):\n",
    "        #         # print(j)\n",
    "        #         if j< nums[i]:\n",
    "        #             f[i+1][j] = f[i][j]\n",
    "        #         else:\n",
    "        #             f[i+1][j] = max(f[i][j],f[i][j-nums[i]]+1)\n",
    "        # return f[n-1][target] if f[n-1][target] > 0 else -1\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i,c):\n",
    "        #     if i < 0:\n",
    "        #         return 0 if c==0 else -inf\n",
    "        #     if c < nums[i]:\n",
    "        #         return dfs(i-1,c)\n",
    "        #     else:\n",
    "        #         return max(dfs(i-1,c),dfs(i-1,c-nums[i])+1)\n",
    "        # res = dfs(n-1,target)\n",
    "        # return res if res != -inf else -1\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,sum):\n",
    "            if sum == 0:\n",
    "                return 0\n",
    "            elif sum < 0:\n",
    "                return -inf\n",
    "            if i == -1:\n",
    "                return -inf\n",
    "            return max(dfs(i-1, sum - nums[i]) + 1, dfs(i-1, sum))\n",
    "        nums.sort()\n",
    "        idx = bisect_right(nums, target)\n",
    "        if idx == 0:\n",
    "            return -1\n",
    "        ans = dfs(idx  -1, target)\n",
    "        dfs.cache_clear()  # 加上这行\n",
    "        if math.isinf(ans):\n",
    "            return -1\n",
    "        else:\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        @cache\n",
    "        def f(i, rs):\n",
    "            if rs < 0:\n",
    "                return -inf\n",
    "            if rs == 0:\n",
    "                return 0\n",
    "            if i == len(nums):\n",
    "                return -inf\n",
    "            a = f(i+1, rs-nums[i])+1\n",
    "            b = f(i+1, rs)\n",
    "            return max(a, b)\n",
    "        ret = f(0, target)\n",
    "        f.cache_clear()\n",
    "        if ret == -inf:\n",
    "            return -1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:\n",
    "        # 0-1背包问题，元素不能重复选择\n",
    "\n",
    "\n",
    "        # 记忆化搜索\n",
    "        nums.sort()\n",
    "        n = bisect.bisect(nums, target) \n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i < 0:\n",
    "                return 0 if c == 0 else -inf\n",
    "\n",
    "            if nums[i] > c:\n",
    "                return dfs(i - 1, c)\n",
    "            return max(dfs(i - 1, c), dfs(i - 1, c - nums[i]) + 1)\n",
    "\n",
    "        ans = dfs(n - 1, target)\n",
    "        dfs.cache_clear()  # 加上这行\n",
    "        return ans if ans > -inf else -1\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
